{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# SIMPLISTIC INTRODUCTION TO ALGORITHMIC COMPLEXITY\n",
    "<hr style=\"height:2px;color:blue\"/>\n",
    "The most important thing to think about when designing and implementing a program is \n",
    "\n",
    "that it should produce <b>results</b> that can <b>be relied upon</b>.\n",
    "\n",
    "* We want our bank balances to be calculated correctly. \n",
    "* We want the fuel injectors in our auto-mobiles to inject appropriate amounts of fuel.\n",
    "* We would prefer that neither air-planes nor operating systems crash\n",
    "\n",
    "Sometimes <b>performance</b> is an important aspect of <b>correctness</b>.\n",
    "\n",
    "This is most obvious for programs that need to <b>run in real time</b>\n",
    "\n",
    "* A program that warns air-planes of potential obstructions needs to issue the warning before the obstruc-tions are encountered.  \n",
    "\n",
    "Performance can also affect <b>the utility of many non-real-time programs</b>\n",
    "\n",
    "* The number of transactions completed per minute is an im-portant metric when evaluating the utility of database systems.\n",
    "* Users care about the time required to start an application on their phone\n",
    "\n",
    "Writing efficient programs is not easy. The most straightforward solution is often not the most efficient. Computationally efficient algorithms often employ subtle tricks that can make them difficult to understand.\n",
    "\n",
    "Consequently Programmers often <b>increase</b> the <b>conceptual complexity</b> of a program in an effort to <b>reduce</b> its <b>computational complexity</b>.\n",
    "\n",
    "**To do this in a <b>sensible</b> way**，we need to understand how to go about estimating **the computational complexity（计算复杂度)** of a program.\n",
    "\n",
    "\n",
    "* The computational complexity of an algorithm is the amount of **resources** required to run it. \n",
    "\n",
    "Particular focus is given to **time** and **memory** requirements.\n",
    "\n",
    "<b style=\"color:blue\">The  computational complexit of an algorithm  or a computer program :</b>\n",
    "\n",
    "* time: [time complexity(时间复杂度)](https://en.wikipedia.org/wiki/Time_complexity)\n",
    "\n",
    "  * describes the amount of time it takes to run an algorithm.\n",
    "\n",
    "* memory:[space complexity(空间复杂度](https://en.wikipedia.org/wiki/Space_complexity)\n",
    "\n",
    "  * the amount of memory space required to solve an instance of the computational problem as a function of the size of the input.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 Thinking About Computational Complexity\n",
    " \n",
    "### 1.1  Measuring the Run Time of an Algorithm：Time complexity\n",
    "\n",
    "How should one go about answering the question\n",
    "\n",
    "* **How long will the following function take to run?**\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(i):\n",
    "    \"\"\"Assumes i is an int and i >= 0\"\"\"\n",
    "    answer = 1\n",
    "    while i >= 1:\n",
    "        answer *= i\n",
    "        i -= 1\n",
    "    return answer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "One way to measure the time cost of an algorithm is to use the computer’s `clock` to obtain an `actual run time`.\n",
    "\n",
    "This process, called **benchmarking or profiling** tarts by determining the time for several different data sets of the same size and then calculates the averagetime. Next, similar data are gathered for larger and larger data sets. After several such tests,enough data are available to predict how the algorithm will behave for a data set of any size.\n",
    "\n",
    "We could run the program on some input and <b>time</b> it. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Problem Size         Seconds\n",
      "         100           0.001\n",
      "         200           0.007\n",
      "         400           0.038\n",
      "         800           0.220\n",
      "        1600           1.376\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "problemSize = 100\n",
    "print(\"%12s%16s\" % (\"Problem Size\", \"Seconds\"))\n",
    "for count in range(5):\n",
    "    start = time.time()\n",
    "    # The start of the algorithm\n",
    "    for x in range(problemSize):\n",
    "        a=f(problemSize)\n",
    "    # The end of the algorithm\n",
    "    elapsed = time.time() - start\n",
    "    print(\"%12d%16.3f\" % (problemSize, elapsed))\n",
    "    problemSize *= 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "This method permits accurate predictions of the running times of many algorithms. \n",
    "\n",
    "However,there are two major problems with this technique:\n",
    "\n",
    "* `Different hardware` platforms have different processing speeds, so the running times of an algorithm differ from machine to machine. Also, the running time of a program varies with the type of operating system that lies between it and the hardware.\n",
    "Finally, `different programming languages and compilers` produce code whose performance varies. For example, the machine code of an algorithm coded in C usually runs slightly faster than the byte code of the same algorithm in Python. Thus, predictions of performance generated from the results of timing on one hardware or software platform generally cannot be used to predict potential performance on other platforms.\n",
    "\n",
    "* It is impractical to determine the running time for some algorithms with **very large** data sets. For some algorithms, it doesn’t matter how fast the compiled code or the hardware processor is. They are impractical to run with very large data sets on any computer.\n",
    "\n",
    "Although timing algorithms may in some cases be a helpful form of testing, you also might want an estimate of the efficiency of an algorithm that is **independent of a particular hardware or software platform**. \n",
    "\n",
    "We get around the **two** issues by using a more **abstract** measure of time.\n",
    "\n",
    "* Instead of measuring time in microseconds, we measure time in terms of the number of basic `steps` executed by the program\n",
    "\n",
    "This allows us to compare the efficiency of two algorithms by talking about\n",
    "\n",
    "* <b>how the running time of each grows with respect to the sizes of the inputs</b>\n",
    "\n",
    "This method, called **complexity analysis**, measure them independently of platform-dependent timings\n",
    "\n",
    "Of course, the actual running time of an algorithm can depend not only up-on the sizes of the inputs but **also** upon their **values**. \n",
    "\n",
    "For example, the linear search algorithm implemented by\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def linearSearch(L, x):\n",
    "    for e in L:\n",
    "        if e == x:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose that L is a million elements long \n",
    "\n",
    "consider the call\n",
    "\n",
    "```python\n",
    "  linearSearch(L, 3).\n",
    "```\n",
    "* If the first element in L is 3, linearSearch will return True almost **immediately**.\n",
    "\n",
    "* if 3 is not in L, linearSearch will have to examine all one **million** elements before returning False.\n",
    "\n",
    "In general, there are <b>three broad cases</b> to think about：\n",
    "\n",
    "* <b>best-case(最好情况)</b> running time is <b>the minimum running time</b> over all the possible inputs of a given size.\n",
    "\n",
    "  * For linearSearch, the best-case running time is <b>independent of the size of L</b>.\n",
    " \n",
    " \n",
    "* <b>worst-case(最坏情况)</b> running time is <b>the maximum running time</b> over all the possible inputs of a given size. \n",
    "\n",
    "  * For linearSearch, the worstcase running time is <b>linear in the size of the list</b>.\n",
    "\n",
    "\n",
    "* <b>average-case(平均情况)</b> running time is the average running time over all possible inputs of a given size. \n",
    "\n",
    "People usually focus on the <b>worst case</b> : an <b>upper bound</b> on the running time. \n",
    "\n",
    "This is <b>critical</b> in situations where there is <b>a time constraint</b> on how long a computation can take. \n",
    "\n",
    "* It is not good enough to know that **most of the time** the air traffic control system **warns** of impending collisions before they occur\n",
    "\n",
    "\n",
    "> 时间复杂度：算法执行过程中运算次数。\n",
    ">\n",
    ">大O符号表示法：$O(f(n))$，其中$f(n)$表示每行代码执行次数之和，是算法的渐进时间复杂度，亦即考察输入值大小趋近无穷时的情况。\n",
    ">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Measuring the Memory Used by an Algorithm：Space Complexity\n",
    "\n",
    "\n",
    "A complete analysis of the resources used by an algorithm includes the amount of memory  required. \n",
    "\n",
    "Once again, focus on rates of potential growth. Some algorithms require the same amount of memory to solve any problem. \n",
    "\n",
    "Other algorithms require more memory as the problem size gets larger.\n",
    "\n",
    ">空间复杂度:一个算法在运行过程中占用存储空间大小的量度，记做$O(f(n))$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 Order of  Complexity \n",
    "\n",
    "Consider the two following loops.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Problem Size Iterations     \n",
      "          10              10\n",
      "          20              20\n",
      "          40              40\n",
      "          80              80\n"
     ]
    }
   ],
   "source": [
    "problemSize = 10\n",
    "print(\"{:12s} {:15s}\".format(\"Problem Size\", \"Iterations\"))\n",
    "for count in range(4):\n",
    "    number = 0\n",
    "    # The start of the algorithm\n",
    "    for j in range(problemSize):\n",
    "         number += 1\n",
    "    # The end of the algorithm\n",
    "    print(\"{:12d} {:15d}\".format(problemSize, number))\n",
    "    problemSize *= 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Problem Size Iterations     \n",
      "          10             100\n",
      "          20             400\n",
      "          40            1600\n",
      "          80            6400\n"
     ]
    }
   ],
   "source": [
    "problemSize = 10\n",
    "print(\"{:12s} {:15s}\".format(\"Problem Size\", \"Iterations\"))\n",
    "for count in range(4):\n",
    "    number = 0\n",
    "    # The start of the algorithm\n",
    "    for j in range(problemSize):\n",
    "        for k in range(problemSize):\n",
    "            number += 1\n",
    "    # The end of the algorithm\n",
    "    print(\"{:12d} {:15d}\".format(problemSize, number))\n",
    "    problemSize *= 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first loop executes $n$ times for a problem of size $n$. \n",
    "\n",
    "The second loop contains a nested loop that iterates $n^2$ times.\n",
    "\n",
    "The amount of work done by these two algorithms is similar for small values of $n$ but is very different for **large** values of $n$. \n",
    "\n",
    "Figure 3-5 and Table 3-1 illustrate this divergence.\n",
    "\n",
    "Note that:“work” in this case refers to the number of iterations of the `most deeply` nested loop.\n",
    "\n",
    "![](./img/ds/bigo.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The performances of these algorithms differ by an **order** of complexity.\n",
    "\n",
    "The performance of the first algorithm is **linear** in that its work grows in direct proportion to the size of the\n",
    "problem (problem size of 10, work of 10; 20 and 20; and so on). \n",
    "\n",
    "The behavior of the second algorithm is **quadratic** in that its work grows as a function of the square of the problem size\n",
    "(problem size of 10, work of 100). \n",
    "\n",
    "As you can see from the graph and the table, algorithms with linear behavior do less work than algorithms with quadratic behavior for most problem sizes n. \n",
    "\n",
    "In fact, as the problem size gets larger, the performance of an algorithm with the **higher order** of complexity becomes **worse** more quickly\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Several other orders of complexity are commonly used in the analysis of algorithms.** \n",
    "\n",
    "An algorithm has **constant** performance if it requires the same number of operations for any problem size. \n",
    "\n",
    "List indexing is a good example of a constant-time algorithm. This is clearly the best kind of performance to have.\n",
    "\n",
    "Another order of complexity that is better than linear but worse than constant is called **logarithmic**. The amount of work of a logarithmic algorithm is proportional to the $log2$ of the problem size. Thus, when the problem doubles in size, the amount of work only\n",
    "increases by 1 (that is, just add 1)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The work of a **polynomial** time algorithm grows at a rate of $n^k$, where $k$ is a constant greater than 1. Examples are $n^2$, $n^3$, and $n^10$.\n",
    "Although n3 is worse in some sense than n2, they are both of the polynomial order and are better than the next higher order of complexity.\n",
    "\n",
    "An order of complexity that is worse than polynomial is called **exponential**. An example rate of growth of this order is $2^n$. Exponential algorithms are **impractical to run with large problem sizes**. \n",
    "\n",
    "The most common orders of complexity used in the analysis of algorithms are summarized in Figure 3-6 and Table 3-2.\n",
    "\n",
    "![](./img/ds/bigo-orders.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 Big-O Notation\n",
    "\n",
    "\n",
    "An algorithm **rarely** performs a number of operations exactly equal to $n$, $n^2$, or $k^n$. \n",
    "\n",
    "An algorithm usually performs other work in the body of a loop, above the loop, and below the loop.\n",
    "\n",
    "For example, you might more precisely say that an algorithm performs $2n+3$ or $2n^2$ operations. In the case of a nested loop, the inner loop might execute one fewer pass after each pass through the outer loop, so that the total number of iterations might be more like\n",
    "$\\frac{1/2}n^2-\\frac{1/2}n$ , rather than $n^2$. The amount of work in an algorithm typically is the sum of several terms in a polynomial.\n",
    "\n",
    "Whenever the amount of work is expressed as a polynomial, *one term is dominant*. As $n$ becomes large, the dominant term becomes so large that you can *ignore* the amount of work represented by the other terms. Thus, for example, in the polynomial $\\frac{1/2}n^2-\\frac{1/2}n$, you focus on the quadratic term, $\\frac{1/2}n^2$. in effect *dropping* the linear term, $\\frac{1/2}n$, from consideration. \n",
    "\n",
    "You can also *drop*the coefficient $\\frac{1/2}$,because the ratio between $\\frac{1/2}n^2$ and $n^2$ does not change as $n$ grows.\n",
    "\n",
    "For example, if you double the problem size, the run times of algorithms that are  $\\frac{1/2}n^2$ and $n^2$ increase by a\n",
    "factor of $4$. This type of analysis is sometimes called **asymptotic analysis（渐近分析）** because the value of a polynomial asymptotically approaches or approximates the value of its largest term as $n$ becomes very large.\n",
    "\n",
    "One notation that computer scientists use to express the efficiency or computational complexity\n",
    "of an algorithm is called $big-O$ notation. **“O”** stands for **“on the order of”**， a reference to the order of complexity of the work of the algorithm. \n",
    "\n",
    "Thus, for example, the order of complexity of a linear-time is $O(n)$\n",
    "\n",
    "$Big-O$ notation formalizes our discussion of orders of complexity.\n",
    "\n",
    "Some of the most common instances of $BigO$ are listed below. In each case, $n$ is a measure of the size of the inputs to the function.\n",
    "\n",
    "* **$O(1)$** denotes constant running time.\n",
    "\n",
    "\n",
    "\n",
    "* **$O(logn)$** denotes logarithmic running time.\n",
    "\n",
    "\n",
    "* **$O(n)$** denotes linear running time.\n",
    "\n",
    "\n",
    "* **$O(nlogn)$** denotes log-linear running time.\n",
    "\n",
    "\n",
    "* **$O(n^k)$** denotes polynomial running time. Notice that $k$ is a constant.\n",
    "\n",
    "\n",
    "* **$O(c^n)$** denotes exponential running time. Here a constant is being raised to a power based on the size of the input.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4 The Role of the Constant of Proportionality\n",
    "\n",
    "The **constant of proportionality** involves the terms and coefficients that are usually **ignored**\n",
    "during $big-O$ analysis.\n",
    "\n",
    "For example, the work performed by a linear-time algorithm might be expressed as work $2 * size$, where the constant of proportionality, 2 in this case, is work/size.\n",
    "\n",
    "When these constants are large, they may affect the algorithms, particularly for **small- and medium-sized** data sets. \n",
    "\n",
    "For example, no one can ignore the difference between $n$ and $n/2$, when $n$ is $1,000,000$. \n",
    "\n",
    "In the example algorithms discussed thus far, the instructions that execute within a loop are part of the constant of proportionality, as are the instructions that initialize the variables before the loops are entered. \n",
    "\n",
    "When analyzing an algorithm, you must be careful to determine whether any single instruction does work that **varies** with the problem **size**.\n",
    "\n",
    "If that is the case, then the analysis of the work must move down into that instruction.\n",
    "\n",
    "Now try to determine the constant of proportionality. Here is the code:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "work = 1\n",
    "for x in range(problemSize):\n",
    "    work += 1\n",
    "    work -= 1\n",
    "```    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that,\n",
    "\n",
    "aside from the `for` loop itself, there are **three** lines of code, each of them assignment\n",
    "statements. \n",
    "\n",
    "Each of these three statements runs in constant time. Also assume that on each iteration, the overhead of managing the loop, which is hidden in the loop header, runs an instruction that requires constant time. \n",
    "\n",
    "Thus, the amount of abstract work performed by this algorithm is $3n+1$. \n",
    "\n",
    "Although this number is greater than just $n$, the running times for the two amounts of work, $n$ and $3n+1$, increase at a **linear** rate. In other words, their running time is $O(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.7"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
